package com.huang.leetcode.tree;

import com.huang.leetcode.constant.TreeNode;

/**
 * @Author：CreateSequence
 * @Date：2020-07-28 13:57
 * @Description：二叉搜索树中第K小的元素
 * 总结：二叉排序树 =》 中序遍历/递归
 */
public class PB230 {

    int num = 0;
    int res = 0;

    public int kthSmallest(TreeNode root, int k) {
        inOrderFind(root, k);
        return res;
    }

    public void inOrderFind(TreeNode node, int k) {
        if (node == null) {
            return;
        }

        //向左递归
        if (node.left != null) {
            inOrderFind(node.left, k);
        }

        //第k大即第k-1个元素
        if (num++ == k - 1) {
            res = node.val;
            return;
        }

        //向右递归
        if (node.right != null) {
            inOrderFind(node.right, k);
        }
    }

}
